The invention relates to using electronic devices such as computers to solve a class of nonlinear functions, specifically power functions, such as x1/3, x0.76312, x−1/2 and similar functions. More specifically, the invention addresses the case where both the input and output are fixed-point numbers represented in binary format, such as is used in computers and other electronic devices.
Electronic devices such as computers require complex mathematical computations to be performed in order to operate. For example, in a video signal processor, color, contrast and other characteristics that need to be projected or otherwise presented in visual media are quantified in numerical values. Mathematical operations are then performed on these values to enable a device such as a television to operate. These operations need to be finite by their nature so that the device can operate, thus they must be approximated. The performance of a device depends on its ability to efficiently approximate results to data processing equations. One such operation is the approximation of a fixed point number raised to a power. There are a number of conventional techniques that address the problem of generating a fixed point approximation to power functions using electronic hardware and software, particularly in video or audio applications, where voluminous amounts of data needs to constantly and accurately be processes. Even more particularly, high definition media processors require an enormous amount of data processing to enable quality media presentations. Some methods of approximating a power functions include Taylor series approximation, Newton-Raphson method or table lookup. Each of these methods has tradeoffs between complexity in terms of memory or operations, restrictions on the domain and or range of the function to be approximated, and accuracy of the result. For example, a Taylor series is appropriate only if the expansion is around a convenient number and all input values, known in the art as the domain, are close to that number. Otherwise the accuracy suffers. Newton-Raphson is limited because of the processing power required to produce a result. For example, the Newton-Raphson method may operate adequately in some applications for finding the square root of a number, but would not work well for generating the results for the 4/3 or 3/4 powers because of complexity in terms of operations. The memory required for a table lookup is proportional to the domain of the function. Thus, if an application needs a great deal of data, such as audio or video data, a great deal of storage space would be needed to store such tables, and the database operations would further slow down the processing.
The problem with conventional techniques is that there is a good deal of complexity, which translates into a need for a large amount of memory space and a large number of operations to be performed. Limiting these factors correlates to a limit in the domain of possible variables and results. Conventional methods also provide only limited accuracy when approximating power functions using fixed-point arithmetic. Most systems and methods simply use a complex set of lookup tables, or rely on Taylor series approximations that require a relatively large number of mathematical calculations, such as adds and multiplies.
Therefore, there exists a need many fields for an accurate system and method for generating a fixed point approximation that is not burdensome on a processor or on memory of a given device. As will be seen the invention accomplishes this in an elegant manner.